package com.models;

import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MinPQ <Key> implements Iterable<Key> {


    private Key pq[];
    private Comparator<Key> comparator;
    int n;
    public MinPQ(int initCapacity) {
        pq = (Key[]) new Object[initCapacity + 1];
    }
    public MinPQ() {
        this(1);
    }

    MinPQ(int initCapacity, Comparator<Key> comparator) {
        this.comparator = comparator;
        pq = (Key[]) new Object[initCapacity + 1];
    }

    public void insert(Key key) {
       if (n == pq.length)
           resize();
       pq[++n] = key;
       swim(n);
    }

    public Key delMin() {
        if (pq == null || n == 0)
            return null;
        Key retVal = pq[1];
        exch(1, n--);
        sink(1);
        pq[n + 1] = null;
        return retVal;
    }

    private void resize() {
        Key[] newPQ = (Key[]) new Object[2 * n + 1];
        for (int i = 1; i <=n ; i++) {
            newPQ[i] = pq[i];
        }
        pq = newPQ;
    }

    public boolean isEmpty() {
        return n == 0;
    }

    private void sink(int k) {
        while ( 2 * k <= n && greater(k, k * 2)) {
            exch(k, k * 2);
            k = k * 2;
        }
    }
    private void swim(int k) {
        while (k > 1  && greater(k / 2, k)) {
            exch(k, k / 2);
            k = k / 2;
        }
    }

    private void exch(int i, int j) {
        Key tmp = pq[i];
        pq[i] = pq[j];
        pq[j] = tmp;

    }

    private boolean greater(int i, int j) {
        if (comparator == null) {
            return ((Comparable<Key>)pq[i]).compareTo(pq[j]) > 0;
        } else {
            return comparator.compare(pq[i], pq[j]) > 0;
        }
    }

    @Override
    public Iterator<Key> iterator() {
        return null;
    }

    private class HeapIterator implements Iterator<Key> {

        private MinPQ<Key> copy;
        public HeapIterator() {
            if (comparator == null) {
                copy = new MinPQ<>(n);
            } else {
                copy = new MinPQ<>(n, comparator);
            }
            for (int i = 1; i <= n; i++) {
               copy.insert(pq[i]);
            }
        }
        @Override
        public boolean hasNext() {
            return !copy.isEmpty();
        }

        @Override
        public Key next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return copy.delMin();
        }
    }
}
